package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         106,
		Discription: "根据后序遍历和中序遍历还原二叉树",
		Level:       2,
		Labels: map[string]int{
			"递归":  1,
			"二叉树": 1,
		},
	})
}

func BuildTree2(inorder []int, postorder []int) *ds.TreeNode {
	valMap := make(map[int]int, 0)
	for index, val := range inorder {
		valMap[val] = index
	}

	var build func(int, int, int) *ds.TreeNode
	build = func(postStart int, postEnd int, inStart int) *ds.TreeNode {
		if postStart > postEnd {
			return nil
		}

		inIndex := valMap[postorder[postEnd]]
		leftLength := inIndex - inStart
		node := &ds.TreeNode{
			Val: postorder[postEnd],
		}
		node.Left = build(postStart, postStart+leftLength-1, inStart)
		node.Right = build(postStart+leftLength, postEnd-1, inIndex+1)
		return node
	}

	return build(0, len(postorder)-1, 0)
}
